SP4060 KPGAME - A game with probability

dp[0/1][i]dp[0/1][i] :有 ii 颗石子 Alice/Bob 为先手,Alice 赢的概率

PP 为 Alice 拿走石子的概率, QQ 为 Bob 拿走石子的概率。

{dp[0][i]=dp[1][i1]P+dp[1][i](1P)dp[1][i]=dp[0][i1]Q+dp[0][i](1Q)\begin{cases} dp[0][i]=dp[1][i-1] * P+dp[1][i] * (1-P) \\ dp[1][i]=dp[0][i-1] * Q+dp[0][i] * (1-Q) \end{cases}

尝试化简:

dp[0][i]=dp[1][i1]P+dp[1][i](1P)dp[0][i]=dp[1][i-1] * P+dp[1][i] * (1-P)

dp[0][i]=dp[1][i1]P+(dp[0][i1]Q+dp[0][i](1Q))(1P)\Rightarrow dp[0][i]=dp[1][i-1]*P + (dp[0][i-1]*Q + dp[0][i]*(1-Q))*(1-P)

dp[0][i]=dp[1][i1]P+dp[0][i1]Q(1P)+dp[0][i](1Q)(1P)\Rightarrow dp[0][i]=dp[1][i-1]*P + dp[0][i-1]*Q(1-P) + dp[0][i]*(1-Q)*(1-P)

dp[0][i](1(1P)(1Q))=dp[1][i1]P+dp[0][i1]Q(1P)\Rightarrow dp[0][i](1-(1-P)(1-Q))=dp[1][i-1]*P + dp[0][i-1]*Q(1-P)

dp[0][i]=dp[1][i1]P+dp[0][i1]Q(1P)P+QPQ\Rightarrow dp[0][i]=\frac{dp[1][i-1]*P + dp[0][i-1]*Q(1-P)}{P+Q-PQ}

同理可以得到:

dp[1][i]=dp[0][i1]Q+dp[1][i1]P(1Q)P+QPQdp[1][i]=\frac{dp[0][i-1]*Q + dp[1][i-1]*P(1-Q)}{P+Q-PQ}

边界条件:

dp[0][0]=0,dp[1][0]=1dp[0][0]=0,dp[1][0]=1

然后发现可以根据 dp[0/1][i1]dp[0/1][i-1] 的大小关系得到 P,QP,Q

dp[0][i1]>dp[1][i1]dp[0][i-1]>dp[1][i-1],两人都不想拿。

反之两人都想拿。

#include <cstdio>

const int MAXN = 1e5;
int T , n;
double p , q , dp[ 2 ][ MAXN + 5 ];

int main( ) {
	scanf("%d",&T);
	while( T -- ) {
		scanf("%d %lf %lf",&n,&p,&q);
		if( n > MAXN ) n = MAXN;

		dp[ 0 ][ 0 ] = 0 , dp[ 1 ][ 0 ] = 1;
		for( int i = 1 ; i <= n ; i ++ ) {
			double P , Q;
			if( dp[ 0 ][ i - 1 ] <= dp[ 1 ][ i - 1 ] ) P = p     , Q = q;
			else									   P = 1 - p , Q = 1 - q;
			dp[ 0 ][ i ] = ( dp[ 1 ][ i - 1 ] * P + dp[ 0 ][ i - 1 ] * Q * ( 1 - P ) ) / ( P + Q - P * Q );
			dp[ 1 ][ i ] = ( dp[ 0 ][ i - 1 ] * Q + dp[ 1 ][ i - 1 ] * P * ( 1 - Q ) ) / ( P + Q - P * Q );
		}
		printf("%.6f\n", dp[ 0 ][ n ] );
	}
	return 0;
}
/*
1
11115354 0.65433372 0.52248892

0.633701
*/